'''
核心思想是先给出一个初始状态q0，从原始的nfa表格中计算第一行转换的内容，以此计算a,b,...
在计算的过程中，会有新的状态出现，将新的状态加入state中，按照顺序计算state中第二个状态可以到达的
位置，在这个过程中，循环不能停止，应该手动设立结束循环的标志。标志是如果在state中计算到了最后一个状态
证明不能再往下循环，循环结束。

这里需要做说明，就算计算到最后一个状态，如果在最后一个状态中出现了新的状态，在此处停止循环就是错误的
但是算法的逻辑是先计算新的状态并将其加入state，如果在最后一个状态中出现了新的状态，在判断循环是否应该结束
之前，新的状态就会被加入state，所以上述假设不成立，算法依然正确。

在计算的具体步骤中，要考虑一个状态由几个q组成，如果是多个，就要把这些q单独取出来比较，获得一个状态中所有q的
转移状态作为此状态生成的新状态，中间用空格隔开，方便spilt。


'''

dfa_table = []
state = []#存放所有的状态,是table的第一列
#定义的nfc转移表,用编号表示q几，如果能到达，在其中填写到达所需要的字母
#可以从文件中读取
nfa_table = [["ab","a","x","x",],
              ["x","x","ab","x"],
              ["x","x","x","a"],
              ["x","x","x","ab"]]


input_num = 2#转移字符的个数，可输入
sign = ['a','b']#输入，不一定只有两个
#制作state表头
state.append("0 ")
cnt = 0
while 1:#到达循环结束条件的时候退出
    flag = 0#flag=0，说明当前输入为a，flag = 1，说明当前输入为b以此类推
    for j in range(len(sign)):#遍历所有可能的输入
        length = len(state[cnt].split(' ')) - 1
        temp = ""#临时数组，存储新的状态
        for i in range(len(state[cnt].split(' ')) - 1):  # 遍历新的状态中的所有情况
            for k in range(len(nfa_table[0])):#在原始表中查询
                location = int(state[cnt].split(" ")[i])
                if sign[j] in nfa_table[location][k]:
                    if str(k) not in temp:
                        temp = temp + str(k) + " "
        a = state[cnt] + ',' + temp + ',' + sign[j]#规定输入，最后可以通过查找逗号分开
        if(a not in dfa_table):
            dfa_table.append(state[cnt] + ',' + temp + ',' + sign[j])
        if (temp not in state and temp != ""):  # 出现新的状态，加入
            state.append(temp)
            #print(state)
        else:
            flag += 1
    cnt += 1
    if (cnt == len(state) and flag == len(sign)):#当cnt到了状态数组的最后一行，并且flag已经计算过输入的最后一种情况，退出循环
        break
for i in dfa_table:
    print(i)


